#include <dbg.h>
#include <gtest/gtest.h>

using std::vector;

class Solution {
public:
    static int search(const vector<int>& nums, const int target) {
        int left = -1;
        int right = static_cast<int>(nums.size());
        while (left + 1 < right) {
            int mid = left + ((right - left) >> 1);
            if (isBlue(nums, mid, target)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (right == nums.size() || nums[right] != target) {
            return -1;
        }
        return right;
    }

private:
    static bool isBlue(const vector<int>& nums, const int i, const int target) {
        const int end = nums[nums.size() - 1];
        if (nums[i] > end) {
            return target > end && nums[i] >= target;
        }
        return target > end || nums[i] >= target;
    }
};

TEST(TEST1, search) {
    Solution s;
    const vector nums{4, 5, 6, 7, 0, 1, 2};
    EXPECT_EQ(s.search(nums, 0), 4);
}

TEST(TEST2, search) {
    Solution s;
    const vector nums{4, 5, 6, 7, 0, 1, 2};
    EXPECT_EQ(s.search(nums, 3), -1);
}

TEST(TEST3, search) {
    Solution s;
    const vector nums{1};
    EXPECT_EQ(s.search(nums, 0), -1);
}

int main(int argc, char** argv) {
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}